Im Folgenden erfolgt zuerst eine theoretische Beschreibung der Common-Modulus-Attacke und anschließend die Ausführug an einem konkreten Beispiel.

\paragraph{Herleitung Common-Modulus-Attacke}

Aufgabe aus \buchmann{9.7.9} auf Seite 163: Wenn man mit dem RSA-Verfahren eine Nachricht $m$ zweimal verschlüsselt, und zwar mit den öffentlichen Schlüsseln ($n$, $e$) und ($n$, $f$), und wenn $gcd(e, f) = 1$ gilt, dann kann man den Klartext $m$ aus den beiden Schlüsseltexten $c_e = m ^ {e} \tmod n$ und $c_f = m ^ {f} \tmod n$ berechnen. Wie geht das?

\textbf{Lösung}

Da $gcd(e, f) = 1$ gilt auch $x \cdot e + y \cdot f = 1$ (erweiterter euklidischer Algorithmus). Anschließend wendet man dieses Wissen an und erhält $c_e ^ {x} \cdot c_f ^ {y} = (m ^ e) ^x \cdot (m ^ f) ^ y = m ^ {xe} \cdot m ^ {yf} = m ^ {xe + yf} = m ^ {1} = m$

\paragraph{Anwendung Common-Modulus-Attacke}

Aufgabe aus \buchmann{9.7.10} auf Seite 163: Die Nachricht $m$ wird mit den öffentlichen Schlüsseln $(493, 3)$ und $(493, 5)$ verschlüsselt. Die Schlüsseltexte sind $293$ und $421$. Verwenden Sie die Common-Modulus-Attacke um $m$ zu finden.

\textbf{Lösung}

Es wurde $c_e = 293$ verschlüsselt mit $n = 493$ und $e = 3$. Der Schlüsseltext $c_f = 421$ wurde mit dem Schlüssel $n = 493$ und $f = 5$ erzeugt. Man sieht, dass $gcd(e, f) = gcd(3, 5) = 1$. Aus diesem Grund gibt es ein $a \cdot x + b \cdot y = 1$ mit $a = f$ und $b = e$. Die Werte für $x$ und $y$ werden durch Anwendung des erweiterten euklidischen Algorithmus ermittelt.

\begin{center}
\begin{tabular}{|c|ccccc|}
\hline
$k$ & $0$ & $1$ & $2$ & $3$ & $4$ \\
\hline
$r_k$ & $5$ & $3$ & $2$ & $1$ & $0$ \\
$q_k$ & & $1$ & $1$ & $2$ & \\
$x_k$ & $1$ & $0$ & $1$ & \cellcolor{dunkelgrau}$1$ & $3$ \\
$y_k$ & $0$ & $1$ & $1$ & \cellcolor{dunkelgrau}$2$ & $5$ \\
\hline 
\end{tabular}
\end{center}

Der erweiterte euklidische Algorithmus zeigt, dass $5 \cdot (-1) + 3 \cdot 2 = 1$ mit $a = f = 5$, $b = e = 3$, $x = -1$ und $y = 2$ gilt. Um den Klartext $m$ zu erhalten berechnet man $m = c_e ^ {y} \cdot c_f ^ {x} \tmod n = 293 ^ {2} \cdot 421 ^ {-1} \tmod 493$.

Bei $421 ^ {-1}$ handelt es sich um das Inverse von $c_f = 421$. Dieses existiert, da $gcd(c_f, n) = gcd(421, 493) = 1$. Für das Inverse $c_f'$ gilt $c_f \cdot c_f' = 1 \tmod n$. Durch Umformung erhält man $n \cdot x + c_f \cdot c_f' = 1$.

\begin{center}
\begin{tabular}{|c|ccccccccc|}
\hline
$k$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ \\
\hline
$r_k$ & $493$ & $421$ & $72$ & $61$ & $11$ & $6$ & $5$ & $1$ & $0$ \\
$q_k$ & & $1$ & $5$ & $1$ & $5$ & $1$ & $1$ & $5$ & \\
$x_k$ & $1$ & $0$ & $1$ & $5$ & $6$ & $35$ & $41$ & \cellcolor{dunkelgrau}$76$ & $421$ \\
$y_k$ & $0$ & $1$ & $1$ & $6$ & $7$ & $41$ & $48$ & \cellcolor{dunkelgrau}$89$ & $493$ \\
\hline 
\end{tabular}
\end{center}

Der erweiterte euklidische Algorithmus zeigt, dass $n \cdot x + c_f \cdot c_f' = 1$ mit $x = -76$ und 

\begin{center}
\uline{$c_f' = 89$}
\end{center}

Eine Prüfung von $c_f \cdot c_f' = 1 \tmod n$ mit den konkreten Werte $421 \cdot 89 = 1 \tmod 493$ bestätigt, dass $c_f' = 89$ das Inverse von $c_f = 421$ in $\mathbb{Z}/493\mathbb{Z}$ ist.

Nun kann der Klartext ermittelt werden, indem $m = c_e ^ {y} \cdot c_f ^ {x} \tmod n = 293 ^ {2} \cdot 421 ^ {-1} \tmod 493 = 293 ^ 2 \cdot 89 \tmod 493 = 47$ berechnet wird. Der Klartext ist also

\begin{center}
\uuline{$m = 47$}
\end{center}

RSA ist unsicher, wenn zwei Benutzer dasselbe $n$ verwenden!